package com.zdb.datastructures.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 逆波兰计算器
 */
public class ReversePolishCalculator {

    public static void main(String[] args) {

//        String exp = "1+((2+3)*4)-5";
        String exp = "(1+((2+3)*4)-5)/8";

        System.out.println("待计算的表达式：" + exp);

        // 1. 将字符串转成中缀表达式字符列表
        List<String> infixExpList = toInfixExpList(exp);

        System.out.println("中缀表达式：" + infixExpList);

        // 2. 先将中缀表达式转换为后缀表达式  1 2 3 + 4 * + 5 -
        List<String> suffixExpList = toSuffixExpList(infixExpList);
        // 1, 2, 3, +, 4, *, +, 5
        System.out.println("后缀表达式：" + suffixExpList);

        // 3. 计算
        int result = calInfixExpList(suffixExpList);

        System.out.println(result);

    }

    /**
     * 将中缀表达式转换为后缀表达式
     * @param infixExpList
     * @return
     */
    private static List<String> toSuffixExpList(List<String> infixExpList) {

        // 步骤说明：
        // 1. 准备一个字符堆栈s1和一个list s2
        // 2. 从左向右扫描
        // 3. 如果为数字： 直接放到list s2
        // 4. 如果为操作符：
        // 4.1. 如果字符堆栈s1为空，或者栈顶为(，直接压入字符堆栈s1
        // 4.2. 如果优先级大于s1栈顶的操作符，则压入s1
        // 4.3. 如果优先级小于等于s1栈顶的操作符，弹出s1的操作符压入s2,再执行4.1操作

        // 5. 如果为括号
        // 5.1. 如果为(，直接压入s1
        // 5.2. 如果为), 弹出s1中最近一个(的所有字符，并压入s2, 再弹出(丢弃

        // 6. 循环到最后一个字符

        // 7. 将s1中的字符弹出压入s2

        // 8. list s2的字符依次展示即为后缀表达式

        Stack<String> s1 = new Stack<>();
        List<String> s2 = new ArrayList<>();
        for(String s : infixExpList) {
            if(s.matches("\\d+")) {
                s2.add(s);
            } else {
                process4To5(s, s1, s2);
            }
        }

        while(true) {
            if(s1.size() > 0) {
                s2.add(s1.pop());
            } else {
                break;
            }
        }

        return s2;
    }

    private static void process4To5(String s, Stack<String> s1, List<String> s2) {

        if("(".equals(s)) {
            s1.push(s);
        } else if(")".equals(s)) {
            while(true) {
                String tmp = s1.pop();
                if("(".equals(tmp)) {
                    break;
                } else {
                    s2.add(tmp);
                }
            }
        } else {
            if(s1.size() == 0 || "(".equals(s1.peek())) {
                s1.push(s);
            } else {
                if(priority(s) > priority(s1.peek())) {
                    s1.push(s);
                } else {
                    s2.add(s1.pop());
                    // 执行 4.1
                    process4To5(s, s1, s2);
                }
            }
        }
    }

    private static int priority(String oper) {
        switch (oper) {
        case "+":
        case "-":
            return 0;
        case "*":
        case "/":
            return 1;
        default:
            throw new RuntimeException("不支持该操作符" + oper);
        }
    }

    /**
     * 将表达式转成中缀表达式字符列表
     * @param exp
     * @return
     */
    public static List<String> toInfixExpList(String exp) {

        // 把数字进行切割，注意多位的数字
        List<String> list = new ArrayList<>();
        int index = 0;
        while (index < exp.length()) {

            // 数字 需要注意多位的情况，需要判断后面一位是否还是数字，如果不是则要连成一个
            char c = exp.charAt(index);
            // 数字
            if(c >= 48 && c <= 57) {
                String num = "" + c;
                while(true) {
                    if (index + 1 < exp.length()) {
                        char nextC = exp.charAt(index + 1);
                        if(nextC >= 48 && c <= 57) {
                            num += nextC;
                            index++;
                        } else {
                            break;
                        }
                    } else {
                        break;
                    }
                }
                list.add(num);

            } else {
                list.add("" + c);
            }

            index ++;
        }


        return list;
    }

    public static int calInfixExpList(List<String> infixExpList) {

        Stack<String> stack = new Stack<>();
        for(String s : infixExpList) {


            if(s.charAt(0) >= 48 && s.charAt(0) <= 57) {

                stack.push(s);

            } else {
                int num1 = Integer.parseInt(stack.pop());
                int num2 = Integer.parseInt(stack.pop());
                switch (s) {
                case "+":
                    stack.push(num1 + num2 + "");
                    break;
                case "-":
                    stack.push(num2 - num1 + "");
                    break;
                case "*":
                    stack.push(num1 * num2 + "");
                    break;
                case "/":
                    stack.push(num2 / num1 + "");
                    break;
                }
            }
        }

        return Integer.parseInt(stack.pop());
    }
}
